package recursion

import "math"

func invert(i byte) byte {
	return byte(1 - i)
}

func recur(n, k int) byte {
	if n == 1 {
		return 0
	} else {
		len := int(math.Pow(2, float64(n))) - 1
		if k == len/2 {
			return 1
		} else if k > len/2 {
			return invert(recur(n-1, len-1-k))
		} else {
			return recur(n-1, k)
		}
	}
}

// https://leetcode-cn.com/problems/find-kth-bit-in-nth-binary-string/
func FindKthBit(n int, k int) byte {
	return byte(recur(n, k-1))
}
